/*
 * One example for NOI CSP-J Lesson 10:
 * <https://courses.fmsoft.cn/plzs/noijunior-csp-exercises-lower.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 使用邻接表存储有向加权图
using adj_list = vector<vector<vector<int>>>;

// 也可以使用如下数据类型：
// using adj_list = vector<vector<pair<int, int>>>;

// 该函数使用 Dijkstra 算法计算从 `from` 到其他顶点的最短距离
vector<int> dijkstra(adj_list& graph, int from)
{
    int V = graph.size();

    // 创建一个优先队列，存储用于对比的顶点。
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;

    // 也可以如下定义该优先队列：
    // priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // 创建一个从 from 到其他顶点的距离的矢量，并初始化为无限大（INT_MAX)
    vector<int> dist(V, INT_MAX);

    // 将 from 放入优先队列，并将其距离初始化为 0。
    pq.push({0, from});
    dist[from] = 0;

    // 循环处理直到优先队列为空。
    while (!pq.empty()){

        // 优先队列中顶部的顶点是距离最小的顶点，将其弹出。
        int u = pq.top()[1];
        pq.pop();

        // 处理 u 的所有邻接顶点。
        for (auto x : graph[u]){

            int v = x[0];           // 邻接顶点
            int weight = x[1];      // 权重

            // 如果有一条更短的、从 u 到 v 的道路
            if (dist[v] > dist[u] + weight) {
                // 更新 v 的距离
                dist[v] = dist[u] + weight;

                // 将其放入优先队列
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main()
{
    vector<vector<vector<int>>> graph(5);

    graph[0].push_back({1, 4});
    graph[0].push_back({2, 8});
    graph[1].push_back({4, 6});
    graph[2].push_back({3, 2});
    graph[3].push_back({4, 10});

    vector<int> result = dijkstra(graph, 0);

    for (int dist : result)
        cout << dist << " ";

    cout << endl;
    return 0;
}

